﻿using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using System.Text;

namespace Elderos.TextSearchers
{
	public class RabinKarpTokenizedTextSearcher : TokenizedTextSearcherBase
	{
		#region Overrides of TextSearcherBase

		public RabinKarpTokenizedTextSearcher(IStringLoader stringLoader, ITokenizer tokenizer, string tokenDelimitter = "\0") : 
			base(stringLoader, tokenizer)
		{
			_tokenDelimitter = tokenDelimitter;
		}

		private Dictionary<string, StringCluster> _keywords = new Dictionary<string, StringCluster>();

		private HashSet<string> _singleTokenKeywords = new HashSet<string>();

		private int _loadedStringsCount;
		private string _tokenDelimitter;

		public override int LoadedStringsCount
		{
			get { return _loadedStringsCount; }
		}

		protected override IEnumerable<Position> InnerSearch(string[] tokens)
		{
			var result = new List<Position>();

			for (int i = 0; i < tokens.Length; i++)
			{
				string currentToken = tokens[i];

				if (_singleTokenKeywords.Contains(currentToken))
					result.Add(new Position(i, 1));

				StringCluster cluster;
				if (!_keywords.TryGetValue(currentToken, out cluster))
					continue;

				//LengthList array has been sorted during initialization
				foreach (int length in cluster.LengthList)
				{
					if (i + length >= tokens.Length)
						break;
					var pretenderTokens = new List<string>();
					for (int k = i + 1; k <= i + length; k++)
						pretenderTokens.Add(tokens[k]);

					string tokenString = GetJoinedString(pretenderTokens);
					if (cluster.Strings.Contains(tokenString))
						//Adding 1, because the first token included in the length
						//is the next one to the i-th one
						result.Add(new Position(i, length + 1));
				}
			}

			return result;
		}

		protected override void ProcessString(string str)
		{
			string[] stringTokens = Tokenizer.Tokenize(str);

			//ignoring untokenizable strings
			if (stringTokens == null || stringTokens.Length <= 0)
				return;

			_loadedStringsCount++;

			//interning strings to lower memory consumption
			string firstToken = String.Intern(stringTokens[0]);

			if (stringTokens.Length == 1)
			{
				_singleTokenKeywords.Add(firstToken);
				return;
			}

			if (!_keywords.ContainsKey(firstToken))
				_keywords.Add(firstToken, new StringCluster());

			StringCluster cluster = _keywords[firstToken];
			string[] restTokens = stringTokens.Skip(1).Select(String.Intern).ToArray();

			if (!cluster.LengthList.Contains(restTokens.Length))
				cluster.LengthList.Add(restTokens.Length);

			string tokenSuffix = GetJoinedString(restTokens);
			cluster.Strings.Add(tokenSuffix);
		}

		protected override void OnStringsLoaded()
		{
			base.OnStringsLoaded();
			foreach (StringCluster cluster in _keywords.Values)
			{
				cluster.LengthList.TrimExcess();
				cluster.LengthList.Sort();
			}
		}
		#endregion

		private string GetJoinedString(IEnumerable<string> strings)
		{
			return String.Join(_tokenDelimitter, strings);
		}

		private class StringCluster
		{
			public List<int> LengthList = new List<int>(1);
			public HashSet<string> Strings = new HashSet<string>();
		}

	}
}
